package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 二叉搜索树的后序遍历序列
 *
 * @author yuhushuan
 * @date 2020/6/21 22:12
 */
public class _33_1_SequenceOfBST {
    private static boolean isBST(int[] array) {
        if (array == null) {
            return false;
        }
        return isBST(array, 0, array.length - 1);
    }

    private static boolean isBST(int[] array, int start, int end) {
        // 只有一个节点
        if (start == end) {
            return true;
        }
        int root = array[end--];
        int leftLen = 0;
        int rightLen = 0;

        // 序列中的左子树都小于 root 值
        while (start + leftLen <= end
                && array[start + leftLen] < root) {// 二叉搜索树中没有相同值的节点
            leftLen++;
        }
        // 序列中的右子树都大于 root 值
        while (start + leftLen + rightLen <= end &&
                array[start + leftLen + rightLen] > root) {
            rightLen++;
        }
        if (leftLen + rightLen != end - start + 1) {
            return false;
        }
        boolean result = true;
        if (leftLen > 0) {
            result = isBST(array, start, start + leftLen - 1);
        }
        if (result && rightLen > 0) {
            result = isBST(array, start + leftLen, end);
        }
        return result;
    }

    public static void main(String[] args) {
        // 功能测试
        // 序列对应一棵完全二叉树
        print(new int[]{5, 7, 6, 9, 11, 10, 8});
        // 序列对应一棵都没有左子树的二叉树
        print(new int[]{8, 7, 6, 5});
        // 序列对应一棵都没有左子树的二叉树
        print(new int[]{2, 3, 4, 5});
        // 只有一个节点的二叉树
        print(new int[]{7});
        // 没有对应的二叉树
        print(new int[]{7, 4, 6, 5});
        //特殊输入测试 null
        print(null);
    }

    private static void print(int[] array) {
        System.out.println(String.format(Locale.getDefault(),
                "整数序列为：\n%s\n是二叉搜索树的后序遍历序列为：%b\n",
                Arrays.toString(array), isBST(array)));
    }

}
